package merisis.experiments.gcs;

public class GCSearch6 extends AbstractGuessComplemetSearch {

	public long searchAlgoritm(long start, long end, long key) {

		long entrance = (start + end) >> 1;

		long high = end;
		long low = start;
		long topVal;
		long btmVal;
		long entranceVal = access(entrance);
		if (key < entranceVal) {

			low = start;
			btmVal = access(low);
			high = entrance;
			topVal = entranceVal;
		} else if (key > entranceVal) {

			low = entrance;
			btmVal = entranceVal;
			high = end;
			topVal = access(high);
		} else {
			return entrance;
		}

		boolean hit = true;
		long dblkey = key + key;
		while (low <= high) {

			// jumping function
			long didx = high - low;
			long scope = topVal - btmVal;
			long lhsum = low + high;
			long btvalsum = btmVal + topVal;

			long jump_m; // conservative
			double inversedk = didx / scope;
			long g_b = low + (long) ((key - btmVal) * inversedk);
			long g_t = high - (long) ((topVal - key) * inversedk);
			long guessed;
			guessed = lhsum
					- (long) (((double) (btvalsum - dblkey)) * inversedk);
			guessed >>= 1;
			jump_m = lhsum >> 1;

			long jump;
			if (hit)
				jump = guessed;
			else
				jump = jump_m;

//			System.out.println(String.format("w[%d,%d] g(%d,%d)=%d ex=%s", low,
//					high, g_b, g_t, guessed, hit));
//
			long jumpVal;
			jumpVal = access(jump);

			if (key > jumpVal) {

				low = jump;
				btmVal = jumpVal;

				if (jump != jump_m) {
					if ((jump - low) > (high - jump)) {
						// +------c--g-k-+
					} else {
						// +--g-k-c--k---+
						hit = false; // the stake is lost.
					}
				} else {
					hit = true; // The trust to guess is recovered
				}

			} else if (key < jumpVal) {

				if (high == jump) {
					return -low;
				}
				high = jump;
				topVal = jumpVal;

				if (jump != jump_m) {
					if ((jump - low) > (high - jump)) {
						// +-k----c-k-g---+
						hit = false; // the stake is lost.
					} else {
						// +-k-g---c------+
					}
				} else {
					hit = true; // The trust to guess is recovered
				}
			} else
				return jump; // key found
		}

		return -(low + 1); // key not found.
	}
}
